UVA 1658 结点容量拆点最小费用最大流

Posted on | In , ,

给出$n$个点$m$条边的有向带权图，求$1$~$n$的两条不相交(除了起点和终点外没有公共点)的路径，使得权和最小。

题目链接

题解

  • 经典的结点容量问题
  • 直接给每条边流量限制为 $1$，是不可行的，因为还有可能重复经过某些点(例如两个金字塔连在一起)。
  • 把$[2,n-1]$所有点拆成两个点，这两个点之间建一条流量为 $1$，费用为 $0$ 的边，就可以保证不重复经过同一点。
  • 建图后，跑一个流量为 $2$ 的最小费用最大流即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;

const int MAXN = 2100;
const int MAXV = 2100;
const int MAXE = 20 * MAXV;
const int INF = 0x7f7f7f7f;

int n, m, u, v, c;

struct MinCostMaxFlow {
    int head[MAXV];
    int to[MAXE], next[MAXE], cost[MAXE], flow[MAXE];
    int n, ecnt, st, ed;

    void init(int MAX_Size) {
        n = MAX_Size;
        memset(head, -1,sizeof(head));
        ecnt = 0;
    }
    void add_edge(int u, int v, int c,  int w) {
        to[ecnt] = v; flow[ecnt] = c; cost[ecnt] = w; next[ecnt] = head[u]; head[u] = ecnt++;
        to[ecnt] = u; flow[ecnt] = 0; cost[ecnt] = -w; next[ecnt] = head[v]; head[v] = ecnt++;
    }
    bool vis[MAXV];
    int dis[MAXV], pre[MAXV];
    queue<int> que;
    bool spfa() {
        memset(vis, 0, sizeof(vis));
        memset(dis, 0x7f, sizeof(dis));
        dis[st] = 0;
        que.push(st);
        while(!que.empty()) {
            int u = que.front(); que.pop();
            vis[u] = false;
            for(int p = head[u]; ~p; p = next[p]) {
                int &v = to[p];
                if(flow[p] && dis[v] > dis[u] + cost[p]) {
                    dis[v] = dis[u] + cost[p];
                    pre[v] = p;
                    if(!vis[v]) {
                        que.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
        return dis[ed] < INF;
    }

    int maxFlow, minCost;
    pair<int,int>min_cost_flow(int source, int sink) {
        st = source, ed = sink;
        maxFlow = minCost = 0;
        while(spfa() && maxFlow<2) {
            int u = ed, tmp = INF;
            while(u != st) {
                tmp = min(tmp, flow[pre[u]]);
                u = to[pre[u] ^ 1];
            }
            if(tmp+maxFlow>2) tmp=2-maxFlow;
            u = ed;
            while(u != st) {
                flow[pre[u]] -= tmp;
                flow[pre[u] ^ 1] += tmp;
                u = to[pre[u] ^ 1];
            }
            maxFlow += tmp;
            minCost += tmp * dis[ed];
        }
        return {maxFlow,minCost};
    }
}flow;

int main()
{
    while(scanf("%d%d", &n, &m)!=EOF)
    {
    flow.init(2*n);
    for(int i=2;i<=n-1;i++)
    {
        flow.add_edge(i, n+i, 1, 0);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d", &u, &v ,&c);
        if(u>=2 && u<=n-1)
        {
            u=u+n;
        }
        flow.add_edge(u, v, 1, c);
    }
    pair<int,int> k=flow.min_cost_flow(1, n);
    printf("%d\n", k.second);
    }
}